# -*- coding: utf-8 -*-
"""
Created on Sun Sep 30 08:39:15 2018

@author: Administrator
"""
import math 
import random as rd
import numpy as np
import heapq as hp

# 超参数
GA_time = 100
Population = 100
MutationPosibility = 0.01
CrossoverPosibility = 0.6
x_step = 0.01



# 函数定义域
x_max = [10, 10]
x_min = [-10, -10]

GeneNum  = int((x_max[0] - x_min[0]) // x_step)
GeneList = [i for i in range(0, GeneNum)]
StringLength = math.ceil(math.log2(GeneNum))
f_demical_places = 6

# compute the sum of o list    
def sum_list(l):
    sum = 0.0000
    for i in l:
        sum += i
    return sum

# coding 
# from genotype(int_Decimal) to phenotype(str_binary)
def coding(genotype):
    gene_s = '{0:0' + str(StringLength) + 'b}'
    phenotype = gene_s.format(genotype)
    return phenotype

def decode(phenotype):
    x1 = int(phenotype[0:StringLength], 2) * x_step + x_min[0]
    x2 = int(phenotype[StringLength:], 2) * x_step + x_min[0]
    return (round(x1,f_demical_places), round(x2, f_demical_places))

# compute the fitness function
# x1, x2 are the gene (real value)
# single fitness value
def fitness_func(x1, x2):
    if x1 != 0 and x2 != 0:
        return round(math.sin(x1)/x1 * math.sin(x2)/x2, f_demical_places)
    elif x1 != 0 and x2 == 0:
        return round(math.sin(x1)/x1, f_demical_places)
    elif x1 == 0 and x2 != 0:
        return round(math.sin(x2)/x2, f_demical_places)
    else:
        return 1

#compute normalized fitness value (list) 
def fitness(FirstPhenotype):
    x = [list(),list()]
    f = list()    
    for gene in FirstPhenotype:
        x0_temp = int(gene[0:StringLength], 2) * x_step + x_min[0]
        x[0].append(x0_temp)
        x1_temp = int(gene[StringLength:], 2)* x_step + x_min[1]
#        print('left:',gene[0:StringLength], 'right:', gene[StringLength:])
        x[1].append(x1_temp)
        f_temp = fitness_func(x0_temp, x1_temp)
        f.append(f_temp)
    return f

def roulette(f_normal):
#    wheel[i] = 0~i sum(f_normal[i])
    wheel = list()
    sum = 0
    for value in f_normal:
        wheel.append(sum)
        sum += value
        
    wheel_len = len(wheel)
    wheel_point = list()
    for time_i in range(Population):
        wheel_value = rd.random()
        for wheel_pos, value in enumerate(wheel):
            if  wheel_pos == wheel_len - 1:
                wheel_point.append(wheel_pos)
                break
            if wheel_value < value:
                wheel_point.append(wheel_pos - 1)
                break
    return wheel_point

def is_legalgene(gene):
    x0 = int(gene[0:StringLength], 2)
    x1 = int(gene[StringLength:], 2) 
    if x0 in GeneList and x1 in GeneList:
        return True
    else:
        return False

# %% generation = 1
FirstGenotype_x1  = rd.sample(GeneList, Population)
FirstGenotype_x2 = rd.sample(GeneList, Population)

FirstPhenotype = list() #phenotype(str_binary)
for pos in FirstGenotype_x1:
    FirstPhenotype.append(coding(pos))
for i, pos in enumerate(FirstGenotype_x2):
    FirstPhenotype[i] += (coding(pos))
    


#for value in FirstPhenotype:
#    print(is_legalgene(value))


 
def GA(FirstPhenotype):
    # %% generation = 2
    # %% selection and reproduction
    # transfer all f value >= 0
    f = fitness(FirstPhenotype)
    f_positive = list()   
    f_min = min(f)
    if f_min < 0:
        for i, value in enumerate(f):
            f_positive.append(value - f_min)
    else:
        for value in f:
            f_positive.append(value)
        
        
    #normalize f
    sum_f = sum_list(f_positive)
    for i, value in enumerate(f_positive):
        f_positive[i] = round(value / sum_f, f_demical_places)
    wheel_point = roulette(f_positive)
    SecondPhenotype = list()
    for i, point in enumerate(wheel_point):
        SecondPhenotype.append(FirstPhenotype[point])
    
    # %% crossover
    CrossoverTime = Population//2
    CrossoverPos = list()
    SecondPhenotype_C = list(range(0, Population))
    
    HybridOrder = list(range(0, Population))
    rd.shuffle(HybridOrder)
    for i in range(0, CrossoverTime):
        man = HybridOrder[2*i]
        woman = HybridOrder[2*i+1]
        leftgene = SecondPhenotype[man]
        rightgene = SecondPhenotype[woman]
        gamble = rd.random()
        if gamble < CrossoverPosibility:
            # two-point crossover
            guess_p1 = rd.randint(0, 2*StringLength-1)#randint 包括两个边界
            guess_p2 = rd.randint(guess_p1, 2*StringLength-1)
            CrossoverPos.append([guess_p1, guess_p2])
            temp0 = rightgene[0:guess_p1] + leftgene[guess_p1:guess_p2] + rightgene[guess_p2:]
            temp1 = leftgene[0:guess_p1] + rightgene[guess_p1:guess_p2] + leftgene[guess_p2:]
            
            # single-point crossover
#            guess = rd.randint(0, 2*StringLength-1)
#            CrossoverPos.append(guess)
#            temp0 = rightgene[:guess] + leftgene[guess:] 
#            temp1 = leftgene[:guess] + rightgene[guess:] 
            
            if is_legalgene(temp0) and is_legalgene(temp1): 
                SecondPhenotype_C[2*i] = temp0
                SecondPhenotype_C[2*i+1] = temp1
            elif  (not is_legalgene(temp0)) and (not is_legalgene(temp1)):
                SecondPhenotype_C[2*i] = leftgene
                SecondPhenotype_C[2*i+1] = rightgene
            else:
                SecondPhenotype_C[2*i] = temp0 if is_legalgene(temp0) else temp1
                SecondPhenotype_C[2*i+1] = leftgene if f[2*i] > f[2*i+1] else rightgene
        else:
            CrossoverPos.append(0)
            SecondPhenotype_C[2*i], SecondPhenotype_C[2*i+1] = leftgene, rightgene
    
    # %% mutation

    GeneNumPopulation = Population * StringLength * 2 
    MutationTime = math.floor(GeneNumPopulation * MutationPosibility)
    MutationPos = list()
    for i in range(0,MutationTime):
        pos = rd.randint(0, GeneNumPopulation - 1)
        pos_0 = pos // (StringLength * 2)
        pos_1 = pos % (StringLength * 2) 
        MutationPos.append([pos_0, pos_1])
        temp0 = SecondPhenotype_C[pos_0]
        temp1 = temp0[:pos_1] + '1' + temp0[pos_1+1:] if temp0[pos_1] == '0' else temp0[:pos_1] + '0' + temp0[pos_1+1:]
        SecondPhenotype_C[pos_0] = temp1 if is_legalgene(temp1) else temp0
    
#    f0 = fitness(FirstPhenotype)
#    f1 = fitness(SecondPhenotype_C)
#    return FirstPhenotype if f0 > f1 else SecondPhenotype_C    
    return SecondPhenotype_C

max_f = list()
max_f_pos = list()
average_f = list()
PhentypeList = list()
f0 = fitness(FirstPhenotype)

max_f.append(max(f0))
max_f_pos.append(f0.index(max(f0)))
average_f.append(sum_list(f0)/Population)
PhentypeList.append(FirstPhenotype)

Phenotype = FirstPhenotype
for GAGeneration in range(2, GA_time + 1):
    Phenotype = GA(Phenotype)
    f = fitness(Phenotype)
    max_f.append(max(f))
    max_f_pos.append(f.index(max(f)))
    average_f.append(sum_list(f)/Population)
    PhentypeList.append(Phenotype)
    print(GAGeneration , "G is " , max(f))


# %% draw a pic
import matplotlib.pyplot as plt

figsize = 13,11
figure, ax = plt.subplots(figsize=figsize)
font1 = {'family' : 'Arial',
         'weight' : 'normal',
         'size'   : 40,
         }

GA_Timelist = list(range(0,GA_time))
plt.grid(True) ##增加格点
#plt.subplot(211)
plt.ylim(0,1.1)
plt.tick_params(labelsize=43)
plt.xlabel('Generation',font1)
plt.ylabel('Maximum Fintess',font1)
plt.title('multi_point Fitness-Generation Curve'.format(Population),font1)
plt.plot(GA_Timelist, max_f,linewidth=5.0)
#plt.subplot(212) 
#plt.ylim(0,1.5)
#plt.plot(GA_Timelist, average_f)
plt.savefig('F1_nearby_Generation{0}_Population{1}_Step{2}_Mutation{3}_Crossover{4}.jpg'
            .format(GA_time,Population,x_step,MutationPosibility,CrossoverPosibility))
print(max_f[-1])
print(decode(Phenotype[max_f_pos[-1]]))



